Partition-Based Sorting

Sorting based on partition of an array

Sorting algorithms more efficient than the one by transpositions exploit the divide and conquer principle.

Shellsort

Shellsort utilizes the near best cases behaviour of insertion sort. It partition the array and then sort the subarray using insertion sort. Then it make subarrays with smaller gap, meaning fewer and longer subarray.

In [1]:
object ShellSort {
  def sort[T](array: Array[T])(implicit ordering: Ordering[T]): Unit = {
    val gaps = Array(701, 301, 132, 57, 23, 10, 4, 1)
    for (gap <- gaps)
      for (i <- gap until array.length) {
        val temp = array(i)
        var j = i
        while (j >= gap && ordering.compare(array(j - gap), temp) > 0) {
          array(j) = array(j - gap)
          j -= gap
        }
        array(j) = temp
      }
  }
}
Out[1]:
defined object ShellSort

Mergesort

Mergesort consists of two steps. First is to recursively partition the array into subarrays until subarray is the one of length 1, then pick from smaller value to larger one to merge them.

In [2]:
object MergeSort {
  def sort[T](array: Array[T])(implicit ordering: Ordering[T]): Unit = {
    val copy = array.clone
    mergesortRec(copy, array, 0, array.length)

    def mergesortRec(array: Array[T], result: Array[T],
                     start: Int, end: Int): Unit = {
      if (end - start < 2) return
      if (end - start == 2)
        if (ordering.compare(result(start), result(start + 1)) > 0) {
          val temp = result(start)
          result(start) = result(start + 1)
          result(start + 1) = temp
          return
        }

      val mid = (start + end) / 2
      mergesortRec(result, array, start, mid)
      mergesortRec(result, array, mid, end)

      // merge
      var i = start
      var j = mid
      var index = start
      while(index < end) {
        if (j >= end ||
          (i < mid && ordering.compare(array(i), array(j)) < 0)) {
          result(index) = array(i)
          i += 1
        }
        else {
          result(index) = array(j)
          j += 1
        }
        index += 1
      }
    }
  }
}
Out[2]:
defined object MergeSort

Quicksort

Quicksort is the fastest known general-purpose in-memory sorting algorithm in the average case when properly implemented. It select the pivot value from the array, divide it into two subarrays so that one subarray contains only the smaller values than the pivot, another only the larger or equal values. Then it recursively sort the subarrays, then concatenate them.

In [3]:
object QuickSort {
  def sort[T](array: Array[T])(implicit ordering: Ordering[T]): Unit = {
    qSort(array, 0, array.length - 1)

    def qSort(array: Array[T], start: Int, end: Int): Unit = {
      val pivotIndex = findPivot(array, start, end)
      val pivotValue = array(pivotIndex)
      array(pivotIndex) = array(end)
      array(end) = pivotValue
      val rightStart = partition(array, start, end - 1, pivotValue)
      array(end) = array(rightStart)
      array(rightStart) = pivotValue
      if (rightStart - start > 1) qSort(array, start, rightStart - 1)
      if (end - rightStart > 1) qSort(array, rightStart + 1, end)
    }

    def partition(array: Array[T], s: Int, e: Int, pivot: T): Int = {
      var start = s
      var end = e
      do {
        while (ordering.compare(array(start), pivot) < 0) start += 1
        while (end != 0 && ordering.compare(array(end), pivot) > 0) end -= 1
        val temp = array(start)
        array(start) = array(end)
        array(end) = temp
      } while (start < end)
      val temp = array(start)
      array(start) = array(end)
      array(end) = temp
      start
    }

    def findPivot(array: Array[T], start: Int, end: Int): Int = {
      if (end - start >= 2) {
        val mid = (start + end) / 2
        if (ordering.compare(array(start), array(mid)) < 0) {
          if (ordering.compare(array(start), array(end)) >= 0) return start
          else if (ordering.compare(array(mid), array(end)) < 0) return mid
        }
        else {
          if (ordering.compare(array(start), array(end)) < 0) return start
          else if (ordering.compare(array(mid), array(end)) >= 0) return mid
        }
        end
      }
      // only two elements
      else start
    }
  }
}
Out[3]:
defined object QuickSort

Comparision of these algorithms

Since these algorithms are complex compared to transposition sort, analyzing time complexity of them is also not so simple.

Mergesort is the easiest of the three to analyze, and it runs in $\Theta(n)$ time in the best, average, worst cases.

The behaviour of the shellsort heavily depends on how the gap sequence is set. The one used above is called Ciura's sequence and it has the best known performance. The time complexity in the best cases is $\Theta(n)$, however, average and worst case complexity are not known.

The time complexity of quicksort is $\Theta(n\log n)$ for best and average cases. Worst case occurs when pivot is always the lowest or highest value, and time complexity is $\Theta(n^2)$.